package Test;

/**
 * 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
 * 且不能改变原来的数据顺序，返回重新排列后的链表的头指针
 */

/**
 * 将所有小于 x 的节点放在一起 (定义bs be), 将所有大于x 的节点放在一起(定义as ae)
 * 定义一个 cur代替head遍历链表
 * 如果cur的值小于x,如果bs为空时,将cur的值给bs,cur往后走,如果bs不为空时,将cur的值给be,cur往后走,be往后走
 * 如果cur的值大于x,如果as为空时,将cur的值给as,cur往后走,如果as不为空时,将cur的值给ae,cur往后走,ae往后走
 * 上述描述存在空指针异常 , 如果链表中全是小于x的,或者全是大于x的,
 * 如果第一段为空时(bs == null),则返回as , 不为空时,be.next = ae
 * 如果第二段不为空时(as != null),将ae作为尾节点 ae.next == null
 * 最后返回头结点bs
 *
 */
public class Test04 {
    public MySingleList.ListNode partition(MySingleList.ListNode head,int x) {
        MySingleList.ListNode bs = null;
        MySingleList.ListNode be = null;
        MySingleList.ListNode as = null;
        MySingleList.ListNode ae = null;
        MySingleList.ListNode cur = head;

        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //第一段不为空
        if (bs == null) {
            return as;
        }
        be.next = as;
        //第二段不为空
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
}
